package tree;

/**
 * 排序二叉树(查找二叉树)
 * E extends Comparable 指的是该类型  必须要实现Comparable接口
 * 因为排序二叉树中的所有节点都必须能够比较大小.
 */
public class Tree <E extends Comparable<E>>{
    //存放根节点的引用
    private Node root;
    /**
     * Node用于描述二叉树中的一个节点,其中,data用于
     * 存放元素,left和right分别存放左子树和右子树的引用.
     */
    class Node{
        E data;
        Node left;
        Node right;
        //Node(E e){data=e;}
        public Node(E e){
            data=e;
        }

        /**
         * 将元素添加到该节点下面
         *
         */
        public boolean append(E e) {
            //要添加的元素跟当前节点存放的元素相等
            if (data.compareTo(e)==0){
                //排序二叉树不允许重复元素
                return false;
            }
            //要添加的元素比当前节点存放的元素要小
            if (data.compareTo(e)>0){
                //添加到当前节点的左子树
                if (left==null){
                    //当前节点的左子树为空,则该元素成为该节点的左子树
                    left=new Node(e);
                    return true;
                }else{
                    //当前节点的左子树不为空,则递归调用.
                    return left.append(e);
                }
            }else{
                //添加到当前节点的右子树
                if (right==null){
                    //当前节点的右子树为空,则该元素成为该节点的右子树
                    right=new Node(e);
                    return true;
                }else{
                    //当前节点的右子树不为空,则递归调用.
                    return right.append(e);
                }
            }

        }
    }

    /**
     * 将元素添加到二叉树里面
     * @param e  要添加的元素
     * @return   添加成功,返回true
     */
    public boolean add(E e){
        //如果二叉树为空,则新节点成为根节点
        if (root==null){
            root=new Node(e);
            return true;

        }
        //如果二叉树不为空,则新添加的元素要加到根节点下面
        return root.append(e);
    }
}
